# -*- coding: utf-8 -*-
"""
Created on Tue Nov 20 23:26:36 2018

@author: Administrator
"""
"""
 递归
 能用递归解决的问题，必须满足以下两个条件：

 (1)一个问题能够缩减成规模更小，且与原问题有着相同求解方法的问题；
 (2)存在一个能让递归调用退出的简单出口

 递归转非递归算法
 函数在调用时，需要在栈中分配新的帧，将返回地址、调用参数、局部变量入栈
 递归调用越深，占用的栈空间越多，如果过深，就会导致栈溢出
 递归函数：尾递归、非尾递归

 尾递归函数
 指函数的最后一个动作是调用函数自身的递归函数，其往往具有很好的优化效率
"""

class Recurtion:

    # 考试题1 小明和女朋友买士力架吃，先是女朋友吃所有的一般，小明吃1个，
    # 第二天，女朋友吃了一般，小明还是吃1个，这样一直吃下去，
    # 直到第6天时，剩下1个。问小明买了几个?
    # 一般递归方法
    # 分析：
    #count(6) = count(5) // 2 - 1  = 1
    #count(5) = (count(6) + 1 ) * 2 
    def count(self, day):
        if day == 6:
            return 1
        else:
            return (self.count(day + 1) + 1) * 2

    # 尾递归
    # 尾递归每次调用下层递归并没有申请新的栈空间，而是更新当前帧的局部数据，重复使用当前帧，
    # 所以不管有多少层尾递归调用都不会栈溢出，这也是使用尾递归的意义所在。
    def count_tail_recur(self, day, rest):
        
        if day == 1:
            return rest
        else:
            total = (rest + 1) * 2
            return self.count_tail_recur(day - 1, total)
        
    # 用栈改为非递归方法
    
    # 例2 判断一个序列是否是回文串（形如“level”, "abba"这样的字符串）
    # 尾递归
    def is_palin_string(self, string):
        if len(string) == 0 or len(string) == 1:
            return True
        if string[0] != string[-1]:
            return False
        return self.is_palin_string(string[1:-1])

    # 循环法
    def is_palin_string_non(self, string):
        if len(string) == 0 or len(string) == 1:
            return True
        head = 0
        rear = len(string) - 1
        while head <= rear:
            if string[head] != string[rear]:
                return False
            head += 1
            rear -= 1
        return True
    
if __name__ == "__main__":
    cur = Recurtion()
    print(cur.is_palin_string("11211"))
#    print(cur.is_palin_string_non("1"))
#    print(cur.is_palin_string_non("11"))
    print(cur.is_palin_string_non("11211"))

# 递归函数：fact(n) = fact(n -1) * n
# 理论上 所有的递归函数都可以写成循环方式
# 使用递归函数，需要防止栈溢出
def fact(n):
    if n==1:
        return 1
    return n * fact(n - 1)

print(fact(10))

# 如果递归调用的层数过深，会造成栈溢出
# 解决递归调用栈溢出的方法是 尾递归优化
# 尾递归指，函数在返回的时候，调用自身，并且return语句不能包含表达式

# 编译器或者解释器会对尾递归做优化，使递归本身无论调用多少次
# 都只占一个帧 不出现栈溢出的情况

def fact2(n):
    return fact_iter(n, 1)

def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num - 1, num * product)

#fact2(100000000000000)  # 经测试 还是会出现栈溢出现象
# python 标准的解释器 没有针对尾递归做优化 还是会出现栈溢出问题